<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
        // 前序遍历：中左右
        // 中序遍历：左右中
        // 后续便利：右左中

        function TreeNode(val) {
            this.val = val;
            this.left = this.right = null;
        }
        var nodeObj1 = [1, 2, 4, 7, 3, 5, 6, 8]; //前序
        var nodeObj2 = [4, 7, 2, 1, 5, 3, 8, 6]; //中序

        function reConstructBinaryTree(pre, vin) {
            if (!pre.length || !vin.length) return false;
            const rootVal = pre[0];
            const node = new TreeNode(rootVal);
            let i = 0;
            for (; i < vin.length; i++) {
                if (vin[i] === rootVal) break;
            }
            node.left = reConstructBinaryTree(pre.slice(1, i + 1), vin.slice(0, i));
            node.right = reConstructBinaryTree(pre.slice(i + 1), vin.slice(i + 1));
            return node;
        }
        console.log(reConstructBinaryTree(nodeObj1, nodeObj2))
    </script>
</body>

</html>